package pri.zjy.string;

/**
 * @author zhangjy
 * @description 判断子序列
 * <p>
 * 给定字符串 s 和 t ，判断 s 是否为 t 的子序列。
 * <p>
 * 字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。（例如，"ace"是"abcde"的一个子序列，而"aec"不是）。
 * <p>
 * 提示：
 * <p>
 * 0 <= s.length <= 100
 * 0 <= t.length <= 10^4
 * 两个字符串都只由小写字符组成。
 * <p>
 * 进阶：
 * <p>
 * 如果有大量输入的 S，称作 S1, S2, ... , Sk 其中 k >= 10亿，你需要依次检查它们是否为 T 的子序列。在这种情况下，你会怎样改变代码？
 * @date 2025/4/3 10:33
 */
public class IsSubsequence_392 {

    public static void main(String[] args) {
        IsSubsequence_392 isSubsequence392 = new IsSubsequence_392();
        String s = "";
        String t = "asd";
        System.out.println(isSubsequence392.isSubsequence(s, t));

        // TODO 本题进阶问题可用 动态规划 完成，后续开始DP刷题再做

    }

    /**
     * 官解-双指针
     * <p>
     * 由个解可知，当s在t中找到所有相同字符，s就是t的子序列，此时一定有 i == s.length()；
     * 另外，由于循环条件是while (i < n && j < m) 和 最后 return i == n; 他们共同确保s、t为空字符串的场景也能正确判断。
     */
    public boolean isSubsequence2(String s, String t) {
        int n = s.length(), m = t.length();
        int i = 0, j = 0;
        while (i < n && j < m) {
            if (s.charAt(i) == t.charAt(j)) {
                i++;
            }
            j++;
        }
        return i == n;
    }

    /**
     * 个解- 双指针；
     * <p>
     * 分析：
     * 题目说，字符串的一个子序列s是原始字符串t删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。
     * 也就说，在不改变t字符相对位置的前提下，只要其中有s的所有字符，且顺序一致，就表明s是子序列；
     * 注，当s、t是空字符串是要考虑。
     * <p>
     * 复杂度：
     * T(n) = O(m)，其中m为字符串s、t长度最大值；
     * S(n) = O(1)。
     */
    public boolean isSubsequence(String s, String t) {
        // s空字符
        if (s.isEmpty()) return true;
        // s不是空字符，t是一个空字符
        if (t.isEmpty()) return false;

        int i = 0, j = 0;
        // 遍历s、t
        // 两者的字符相同，则i++、j++；否则，只j++
        while (j < t.length()) {
            if (s.charAt(i) == t.charAt(j)) {
                // 按顺序找到s的最后一个字符
                if (i == s.length() - 1) return true;
                i++;
            }
            j++;
        }
        return false;
    }

}
